Field
Various clients may benefit from techniques and devices for authentication and retrievability of stored data in a server. For example, a client may benefit from a dynamic proof of retrievability scheme in a cloud based server.
Description of the Related Art
Storage outsourcing applications have become increasingly popular in cloud based computing. These applications offer various benefits which involve economies of scale and general accessibility. When a cloud storage provider is untrustworthy, an important challenge is presented in offering provable outsourced storage guarantees.
In particular, clients search for authenticated storage and retrievability as two such guarantees. Authenticated storage refers to the client may wanting to verify that data fetched from the server is correct, where correctness includes both authenticity and freshness. Retrievability, on the other hand, refers to the client needing assurance that the server is indeed storing all of the client's data, and that no data loss has occurred.
Proof of Retrievability (POR) provides a method by which a client can have these provable outsourced storage guarantees without having the client individually check each stored data block in the cloud server. In general, POR enables the client to audit data blocks on the server side storage, and be able to prove that the server side storage possesses the data without having to individually download and check all the data blocks. This auditing process is more efficient, and demands a fractional amount of the bandwidth needed to download individual files.
While many static POR schemes have been constructed, an efficient light-weight dynamic POR construction with manageable bandwidth overhead and client side computation is lacking. A dynamic POR scheme, however, presents the additional challenge of needing to check the authenticity and retrievability of data blocks which are either continuously or discretely being updated.
Another scheme used to audit outsourced data is called Proofs of Data Possession (PDP). PDP, however, provides much weaker security guarantees than PoR. With PDP, a server that has lost a small number of data blocks can pass an audit with significant probability. A successful POR, on the other hand, ensures that the server maintains knowledge of all outsourced data block, as opposed to storing most of the data as ensured by PDP.
An approach which shares a similar defect to PDP is a strawman approach, which involved the client attaching a Message Authentication Code (MAC) to every block before uploading it to the server. When using MACs, however, even if the server has lost a small number of blocks, it can still pass the audit with significant probability.
In order to boost detection probability, some approaches have relied on redundant coding known as erasure codes. As an example, if the client outsources a total of n blocks, which are erasure coded into m=(1+c) n blocks for some constant 0<c≤1, and knowledge of any block n suffices to recover the entire dataset, the server has to delete at least cn blocks to actually incur data loss. If the server deletes this many blocks, however, it will fail the audit protocol with overwhelming probability of at least 1−1/(1+c)λ, where λ represents number of random code block checked during authentication.
Another tremendous obstacle involved in using erasure codes has to do with dynamic use of data. If the client wants to update a single block n, the client can also be forced to update all the cn parity blocks, which can be very expensive and costly. As such, a better POR scheme needs to be developed to deal with dynamic data.
A recent impractical dynamic POR construction, which attempts to support updating cn parity blocks, involves the use of an Oblivious RAM (ORAM). This method attempts to achieve asymptotic efficiency in the presence of updates with constant client storage by relying on an ORAM. ORAM is a rather heavy-weight cryptographic primitive, and even the fastest known constructions of ORAM incur a large bandwidth overhead in practice. As an example, known ORAM constructions demand that over 400 blocks be transferred between a client and a server for a single data access. Therefore, the use of ORAM to address dynamic POR construction is impractical.
Certain embodiments of the claimed invention provide an efficient implementation of a dynamic POR scheme whose bandwidth cost can be comparable to a Merkle hash tree.